#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int fib(int N) {
        this->memo = vector<int>(N + 1, -1);
        return fibf(N);
    }
private:
    int fibf(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (memo[n] == -1) {
            memo[n] = fibf(n - 1) + fibf(n - 1);
        }
        return memo[n];
    }
    vector<int> memo;
};

int main(int argc, char *argv[])
{
    Solution s;
    int num;
    
    cout << "Please input the nums of fib: ";
    cin >> num;
    
    cout << "Sum: " << s.fib(num) << endl;

    return 0;
}
